/*
	alphabeta.cc	Alpha-Beta Pruning
	Copyright (c) 2000, 2001, 2002, 2003, 2004, 2005 Kriang Lerdsuwanakij
	email:		lerdsuwa@users.sourceforge.net

	This program is free software; you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation; either version 2 of the License, or
	(at your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with this program; if not, write to the Free Software
	Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/

#include "boardio.h"
#include "hash.h"
#include "alphabeta.h"
#include "iter.h"
#include "pattern.h"
#include "parity.h"
#include <stdlib.h>
#include <pthread.h>
#include <string>
#include <iostream>
#include <fstream>
using namespace std;

/*************************************************************************
	Evaluator randomness
*************************************************************************/

static int	randomness = 0;
static int	randomness_mod = 1;

const bool	DEBUG_ALPHA_BETA = false;
ofstream	*debug_stream;
int		debug_indent = 0;
string		debug_file;

void set_eval_random(int r)
{
	randomness = r;
	randomness_mod = 2 * r + 1;
}

int get_eval_random()
{
	return randomness;
}

inline int get_random()
{
	if (randomness)
		return (rand() % randomness_mod) - randomness;
	else
		return 0;
}

/*************************************************************************
	Mid game strategy
*************************************************************************/

class midgame_strategy {
	public:
		static int	board_score(search_info &info, int player)
		{
			pthread_testcancel();
			if (info.board->board_black_score() == 0
			    || info.board->board_white_score() == 0)
				return end_board_score(info);
			return pattern_eval(info.board)
			       + parity_eval_alpha_beta(info, player);
		}
		static int	end_board_score(search_info &info)
		{
			pthread_testcancel();
			int score = info.board->board_diff_score();
			if (score > 0)
				return MAX_SCORE-1;	// Required to store move for alphabeta
			else if (score < 0)
				return MIN_SCORE+1;	// Required to store move for alphabeta
			return 0;
		}
		static void	log_position(int /*pos*/) {}
		typedef	midgame_strategy next_strategy;
		typedef board_endgame_iterator iterator;
};

/*************************************************************************
	End game strategy
*************************************************************************/

class endgame_strategy {
	public:
		static int	board_score(search_info &info, int /*player*/) { 
			pthread_testcancel();
			return info.board->board_diff_score();
		}
		static int	end_board_score(search_info &info)
		{
			pthread_testcancel();
			return info.board->board_diff_score();
		}
		static void	log_position(int /*pos*/) {}
		typedef	endgame_strategy next_strategy;
		typedef board_endgame_iterator iterator;
};

/*************************************************************************
	Mid game strategy with randomness
*************************************************************************/

class midgame_strategy_with_random {
	public:
		static int	board_score(search_info &info, int player)
		{
			pthread_testcancel();
			if (info.board->board_black_score() == 0
			    || info.board->board_white_score() == 0)
				return end_board_score(info);
			return get_random() + pattern_eval(info.board)
			       + parity_eval_alpha_beta(info, player);
		}
		static int	end_board_score(search_info &info)
		{
			pthread_testcancel();
			int score = info.board->board_diff_score()+get_random();
			if (score > 0)
				return MAX_SCORE-1;	// Required to store move for alphabeta
			else if (score < 0)
				return MIN_SCORE+1;	// Required to store move for alphabeta
			return 0;
		}
		static void	log_position(int /*pos*/) {}
		typedef	midgame_strategy_with_random next_strategy;
		typedef board_endgame_iterator iterator;
};

/*************************************************************************
	End game strategy with randomness
*************************************************************************/

class endgame_strategy_with_random {
	public:
		static int	board_score(search_info &info, int /*player*/) {
			pthread_testcancel();
			return info.board->board_diff_score()+get_random();
		}
		static int	end_board_score(search_info &info)
		{
			pthread_testcancel();
			return info.board->board_diff_score()+get_random();
		}
		static void	log_position(int /*pos*/) {}
		typedef	endgame_strategy_with_random next_strategy;
		typedef board_endgame_iterator iterator;
};

/*************************************************************************
	Alpha-beta pruning
*************************************************************************/

static byte_board_info	board_buffer[NUM_MOVE];

// color = color to play
template <class strategy>
int	temp_alpha_beta(search_info &info, int alpha, int beta, int color,
			int depth, int *store_pos = 0)
{
	static	int dir_count[NUM_DIR];

	if (DEBUG_ALPHA_BETA)
		print_board(*debug_stream, info.board, debug_indent);

	int	move = info.board->get_num_move();
	if (move == NUM_MOVE) {
		int score = info.board->board_diff_score();
		if (DEBUG_ALPHA_BETA) {
			print_indent(*debug_stream, debug_indent);
			*debug_stream << "*** Diff score " << score << "***\n";
		}
		return score;
	}
	if (depth <= 0 && !store_pos) {
		int score = strategy::board_score(info, color);
		if (DEBUG_ALPHA_BETA) {
			print_indent(*debug_stream, debug_indent);
			*debug_stream << "*** Leaf score " << score << "***\n";
		}
		return score;
	}
	depth--;

	int		a = alpha, b = beta;
	typename strategy::iterator	iter(info.empties);
				// move >= 0 && move <= 59
	byte_board_info	*board_new = board_buffer+move;
	int		best_pos = POS_PASS, last_pos = POS_PASS;

	trans_board	*t = 0;
				// FIXME: Disable caching for now since
				// pruned score may be stored instead of
				// real one
	if (!store_pos) {
		t = get_hash_board(info.board, color);
//		if (t && t->score != INVALID_SCORE)
//			return t->score;
	}

	if (color == BLACK) {		// Max black's score
		iter.init_pos();	// FIXME: Optimize speed
		int max_a = MIN_SCORE;
		do {
			if (info.board->can_play(color, iter.pos, dir_count)) {

				strategy::log_position(iter.pos);

				last_pos = iter.pos;

				if (DEBUG_ALPHA_BETA) {
					*debug_stream << '\n';
					print_indent(*debug_stream, debug_indent);
					*debug_stream << "Player BLACK   Move ";
					print_pos(*debug_stream, iter.pos);
					*debug_stream << '\n';
					debug_indent += 4;
				}

				*board_new = *info.board;
				board_new->place_piece(color, iter.pos, dir_count);

				byte_board_info *save_board = info.board;
				info.board = board_new;

				iter.remove_current();
				int new_a = temp_alpha_beta<typename strategy::next_strategy>
						(info, a, b, WHITE, depth);
				iter.restore_current();

				info.board = save_board;

				if (DEBUG_ALPHA_BETA) {
					debug_indent -= 4;
					print_indent(*debug_stream, debug_indent);
					*debug_stream << "Score " << new_a << '\n';
				}

				if (new_a > a) {
					a = new_a;
					max_a = new_a;
					best_pos = iter.pos;

					if (a >= b)
						break;
				}
				else if (new_a > max_a) {
					max_a = new_a;
					best_pos = iter.pos;
				}
			}
		} while (iter.next());

		if (last_pos != POS_PASS) {
						// At least one valid moves
						// found
			if (store_pos) {
				*store_pos = best_pos;
			}
			store_hash_board(t, max_a);
			return a;
		}
		else if (info.board->can_play(switch_color(color))) {	// FIXME: Optimize speed
						// Have to pass.
						// Game not over yet.
			if (store_pos) {
				*store_pos = POS_PASS;
			}

			if (DEBUG_ALPHA_BETA) {
				*debug_stream << '\n';
				print_indent(*debug_stream, debug_indent);
				*debug_stream << "Player BLACK   PASS\n";
				debug_indent += 4;
			}

			int score = temp_alpha_beta<typename strategy::next_strategy>
				      (info, a, b, switch_color(color), depth+1, 0);
			store_hash_board(t, score);

			if (DEBUG_ALPHA_BETA) {
				debug_indent -= 4;
			}

			return score;
		}
		else {
						// No one can play.  Game over
			if (store_pos) {
				*store_pos = POS_PASS;
			}
			int score = strategy::end_board_score(info);
			store_hash_board(t, score);
			return score;
		}
	}
	else {				// Min black's score
		iter.init_pos();
		int min_b = MAX_SCORE;
		do {
			if (info.board->can_play(color, iter.pos, dir_count)) {

				strategy::log_position(iter.pos);

				last_pos = iter.pos;

				if (DEBUG_ALPHA_BETA) {
					*debug_stream << '\n';
					print_indent(*debug_stream, debug_indent);
					*debug_stream << "Player WHITE   Move ";
					print_pos(*debug_stream, iter.pos);
					*debug_stream << '\n';
					debug_indent += 4;
				}

				*board_new = *info.board;
				board_new->place_piece(color, iter.pos, dir_count);

				byte_board_info *save_board = info.board;
				info.board = board_new;

				iter.remove_current();
				int new_b = temp_alpha_beta<typename strategy::next_strategy>
						(info, a, b, BLACK, depth);
				iter.restore_current();

				info.board = save_board;

				if (DEBUG_ALPHA_BETA) {
					debug_indent -= 4;
					print_indent(*debug_stream, debug_indent);
					*debug_stream << "Score " << new_b << '\n';
				}

				if (new_b < b) {
					b = new_b;
					min_b = new_b;
					best_pos = iter.pos;

					if (a >= b)
						break;
				}
				else if (new_b < min_b) {
					min_b = new_b;
					best_pos = iter.pos;
				}
			}
		} while (iter.next());

		if (last_pos != POS_PASS) {
						// At least one valid moves
						// found
			if (store_pos) {
				*store_pos = best_pos;
			}
			store_hash_board(t, min_b);
			return b;
		}
		else if (info.board->can_play(switch_color(color))) {
						// Have to pass.
						// Game not over yet.
			if (store_pos) {
				*store_pos = POS_PASS;
			}

			if (DEBUG_ALPHA_BETA) {
				*debug_stream << '\n';
				print_indent(*debug_stream, debug_indent);
				*debug_stream << "Player WHITE   PASS\n";
				debug_indent += 4;
			}

			int score = temp_alpha_beta<typename strategy::next_strategy>
				      (info, a, b, switch_color(color), depth+1, 0);
			store_hash_board(t, score);

			if (DEBUG_ALPHA_BETA) {
				debug_indent -= 4;
			}

			return score;
		}
		else {
						// No one can play.  Game over
			if (store_pos) {
				*store_pos = POS_PASS;
			}
			int score = strategy::end_board_score(info);
			store_hash_board(t, score);
			return score;
		}
	}
}

// color = color to play
template <class strategy>
int	temp_alpha_beta_new(search_info &info, int alpha, int beta, int color,
			int depth, int *store_pos = 0)
{
	static	int dir_count[NUM_DIR];

	if (DEBUG_ALPHA_BETA)
		print_board(*debug_stream, info.board, debug_indent);

	int	move = info.board->get_num_move();
	if (move == NUM_MOVE) {
		int score = info.board->board_diff_score();
		if (DEBUG_ALPHA_BETA) {
			print_indent(*debug_stream, debug_indent);
			*debug_stream << "*** Diff score " << score << "***\n";
		}
		return score;
	}
	if (depth <= 0 && !store_pos) {
		int score = strategy::board_score(info, color);
		if (DEBUG_ALPHA_BETA) {
			print_indent(*debug_stream, debug_indent);
			*debug_stream << "*** Leaf score " << score << "***\n";
		}
		return score;
	}
	depth--;

	int		a = alpha, b = beta;
	typename strategy::iterator	iter(info.empties);
				// move >= 0 && move <= 59
	byte_board_info	*board_new = board_buffer+move;
	int		best_pos = POS_PASS, last_pos = POS_PASS;

	trans_board	*t = 0;
				// FIXME: Disable caching for now since
				// pruned score may be stored instead of
				// real one
	if (!store_pos) {
		t = get_hash_board(info.board, color);
		if (t && t->score != INVALID_SCORE)
			return t->score;
	}

	if (color == BLACK) {		// Max black's score
		iter.init_pos();	// FIXME: Optimize speed
		int max_a = MIN_SCORE;
		do {
			if (info.board->can_play(color, iter.pos, dir_count)) {

				strategy::log_position(iter.pos);

				last_pos = iter.pos;

				if (DEBUG_ALPHA_BETA) {
					*debug_stream << '\n';
					print_indent(*debug_stream, debug_indent);
					*debug_stream << "Player BLACK   Move ";
					print_pos(*debug_stream, iter.pos);
					*debug_stream << '\n';
					debug_indent += 4;
				}

				*board_new = *info.board;
				board_new->place_piece(color, iter.pos, dir_count);

				byte_board_info *save_board = info.board;
				info.board = board_new;

				iter.remove_current();
				int new_a = temp_alpha_beta<typename strategy::next_strategy>
						(info, a, b, WHITE, depth);
				iter.restore_current();

				info.board = save_board;

				if (DEBUG_ALPHA_BETA) {
					debug_indent -= 4;
					print_indent(*debug_stream, debug_indent);
					*debug_stream << "Score " << new_a << '\n';
				}

				if (new_a > a) {
					a = new_a;
					max_a = new_a;
					best_pos = iter.pos;

					if (a >= b)
						break;
				}
				else if (new_a > max_a) {
					max_a = new_a;
					best_pos = iter.pos;
				}
			}
		} while (iter.next());

		if (last_pos != POS_PASS) {
						// At least one valid moves
						// found
			if (store_pos) {
				*store_pos = best_pos;
			}
			store_hash_board(t, max_a);
			return a;
		}
		else if (info.board->can_play(switch_color(color))) {	// FIXME: Optimize speed
						// Have to pass.
						// Game not over yet.
			if (store_pos) {
				*store_pos = POS_PASS;
			}

			if (DEBUG_ALPHA_BETA) {
				*debug_stream << '\n';
				print_indent(*debug_stream, debug_indent);
				*debug_stream << "Player BLACK   PASS\n";
				debug_indent += 4;
			}

			int score = temp_alpha_beta<typename strategy::next_strategy>
				      (info, a, b, switch_color(color), depth+1, 0);
			store_hash_board(t, score);

			if (DEBUG_ALPHA_BETA) {
				debug_indent -= 4;
			}

			return score;
		}
		else {
						// No one can play.  Game over
			if (store_pos) {
				*store_pos = POS_PASS;
			}
			int score = strategy::end_board_score(info);
			store_hash_board(t, score);
			return score;
		}
	}
	else {				// Min black's score
		iter.init_pos();
		int min_b = MAX_SCORE;
		do {
			if (info.board->can_play(color, iter.pos, dir_count)) {

				strategy::log_position(iter.pos);

				last_pos = iter.pos;

				if (DEBUG_ALPHA_BETA) {
					*debug_stream << '\n';
					print_indent(*debug_stream, debug_indent);
					*debug_stream << "Player WHITE   Move ";
					print_pos(*debug_stream, iter.pos);
					*debug_stream << '\n';
					debug_indent += 4;
				}

				*board_new = *info.board;
				board_new->place_piece(color, iter.pos, dir_count);

				byte_board_info *save_board = info.board;
				info.board = board_new;

				iter.remove_current();
				int new_b = temp_alpha_beta<typename strategy::next_strategy>
						(info, a, b, BLACK, depth);
				iter.restore_current();

				info.board = save_board;

				if (DEBUG_ALPHA_BETA) {
					debug_indent -= 4;
					print_indent(*debug_stream, debug_indent);
					*debug_stream << "Score " << new_b << '\n';
				}

				if (new_b < b) {
					b = new_b;
					min_b = new_b;
					best_pos = iter.pos;

					if (a >= b)
						break;
				}
				else if (new_b < min_b) {
					min_b = new_b;
					best_pos = iter.pos;
				}
			}
		} while (iter.next());

		if (last_pos != POS_PASS) {
						// At least one valid moves
						// found
			if (store_pos) {
				*store_pos = best_pos;
			}
			store_hash_board(t, min_b);
			return b;
		}
		else if (info.board->can_play(switch_color(color))) {
						// Have to pass.
						// Game not over yet.
			if (store_pos) {
				*store_pos = POS_PASS;
			}

			if (DEBUG_ALPHA_BETA) {
				*debug_stream << '\n';
				print_indent(*debug_stream, debug_indent);
				*debug_stream << "Player WHITE   PASS\n";
				debug_indent += 4;
			}

			int score = temp_alpha_beta<typename strategy::next_strategy>
				      (info, a, b, switch_color(color), depth+1, 0);
			store_hash_board(t, score);

			if (DEBUG_ALPHA_BETA) {
				debug_indent -= 4;
			}

			return score;
		}
		else {
						// No one can play.  Game over
			if (store_pos) {
				*store_pos = POS_PASS;
			}
			int score = strategy::end_board_score(info);
			store_hash_board(t, score);
			return score;
		}
	}
}

/*************************************************************************
	Entry for alpha-beta code
*************************************************************************/

int	midgame_alpha_beta(search_info &info, int alpha, int beta, int color, int depth, int *store_pos)
{
	if (get_eval_random())
		return temp_alpha_beta<midgame_strategy_with_random>
			(info, alpha, beta, color, depth, store_pos);
	else
		return temp_alpha_beta<midgame_strategy>
			(info, alpha, beta, color, depth, store_pos);
}

int	endgame_alpha_beta(search_info &info, int alpha, int beta, int color, int depth, int *store_pos)
{
	if (get_eval_random())
		return temp_alpha_beta<endgame_strategy_with_random>
			(info, alpha, beta, color, depth, store_pos);
	else
		return temp_alpha_beta<endgame_strategy>
			(info, alpha, beta, color, depth, store_pos);
}

/*************************************************************************
	Mid game parameter
*************************************************************************/

static int	midgame_depth;

void	set_midgame_depth(int depth)
{
	midgame_depth = depth;
}

/*************************************************************************
	Control hashed data flushing
*************************************************************************/

// FIXME last_eval not thread-safe

enum	last_eval_type {
	last_eval_none,
	last_eval_midgame,
	last_eval_winlossdraw,
	last_eval_endgame
} last_eval;

void	eval_new_game()
{
	last_eval = last_eval_none;
}

int	eval_midgame(byte_board_info *board, int color, int *store_pos)
{
		// Don't cache results from previous move
	free_hash_all_move();
	last_eval = last_eval_midgame;

	search_info info;
	info.board = board;
	init_endgame_iterator(board, info.empties);

	if (DEBUG_ALPHA_BETA) {
		debug_indent = 0;
		debug_file = "midgame-";
		debug_file += (board->get_num_move()/10 + '0');
		debug_file += (board->get_num_move()%10 + '0');
		debug_file += ".log";
		debug_stream = new ofstream(debug_file.c_str());
	}

	int score = midgame_alpha_beta(info, MIN_SCORE, MAX_SCORE, color, midgame_depth, store_pos);

	if (DEBUG_ALPHA_BETA)
		delete debug_stream;

	return score;
}

int	eval_endgame(byte_board_info *board, int color, int *store_pos)
{
//	if (last_eval != last_eval_endgame) {
		free_hash_all_move();
//		last_eval = last_eval_endgame;
//	}

	search_info info;
	info.board = board;
	init_endgame_iterator(board, info.empties);

	if (DEBUG_ALPHA_BETA) {
		debug_indent = 0;
		debug_file = "endgame-";
		debug_file += (board->get_num_move()/10 + '0');
		debug_file += (board->get_num_move()%10 + '0');
		debug_file += ".log";
		debug_stream = new ofstream(debug_file.c_str());
	}

	int score = endgame_alpha_beta(info, MIN_SCORE, MAX_SCORE, color, 30, store_pos);

	if (DEBUG_ALPHA_BETA)
		delete debug_stream;

	return score;
}

int	eval_winlossdraw(byte_board_info *board, int color, int *store_pos,
			 double komi)
{
//	if (last_eval != last_eval_winlossdraw) {
		free_hash_all_move();
//		last_eval = last_eval_winlossdraw;
//	}

	search_info info;
	info.board = board;
	init_endgame_iterator(board, info.empties);

	if (DEBUG_ALPHA_BETA) {
		debug_indent = 0;
		debug_file = "wld-";
		debug_file += (board->get_num_move()/10 + '0');
		debug_file += (board->get_num_move()%10 + '0');
		debug_file += ".log";
		debug_stream = new ofstream(debug_file.c_str());
	}

	int score = endgame_alpha_beta(info, 
				       static_cast<int>(komi - 1),
				       static_cast<int>(komi + 1), 
				       color, 30, store_pos);

	if (DEBUG_ALPHA_BETA)
		delete debug_stream;

	return score;
}
